package com.bclz.datastructures

import scala.annotation.tailrec


sealed trait List[+A]

case object Nil extends List[Nothing]

case class Cons[+A](head: A, tail: List[A]) extends List[A]

object List {

  def sum(list: List[Int]): Int = list match {

    case Nil => 0
    case Cons(h, t) => h + sum(t)
  }

  def product(list: List[Double]): Double = list match {

    case Nil => 0.0
    case Cons(0.0, _) => 0.0
    case Cons(h, t) => h * product(t)

  }

  //通过伴生对象的apply方法构造这个类型的实例是一种惯例
  //List(1,2,3)就会调用apply方法
  def apply[A](as:A*): List[A]=
    if(as.isEmpty) Nil
    else Cons(as.head,apply(as.tail:_*))    //_*指明参数为类Seq类型(即多个A参数为入参)

  def tail[A](list:List[A]):List[A]=list match {

    case Nil=>throw new Exception("the list is empty...")
    case Cons(_,t) =>t
  }

  def head[A](list:List[A]):A=list match  {

    case Nil=>throw new Exception("the list is empty...")
    case Cons(h,_) =>h
  }

  def setHead[A](replace:A,list: List[A]):List[A]=list match {

    case Nil=>throw new Exception("the list is empty...")
    case Cons(_,t)=>Cons(replace,t)

  }

  @tailrec
  def drop[A](l:List[A],n:Int):List[A]={

    if(n<=0)  l
    else l match {
      case Nil=>Nil
      case Cons(_,t) =>drop(t,n-1)
    }
  }


  def dropWhile[A](l:List[A],f:A=>Boolean): List[A] ={

    import scala.collection.mutable.ListBuffer
    //声明一个可变列表
    val buf=new ListBuffer[A]

    @tailrec
    def dropWhileRecu(l:List[A]):List[A]= l match  {

      case Nil => List(buf.toList:_*)
      case Cons(h,t)=>
        if(!f(h)) buf+=h
        dropWhileRecu(t)
    }
    dropWhileRecu(l)
  }

  //柯里化参数为了更好的类型推导，从左到右
  def dropWhileNew[A](l:List[A])(f:A=>Boolean):List[A]=dropWhile(l,f)

  def foldRight[A,B](l:List[A],b:B)(f:(A,B)=>B): B = l match  {
    case Nil => b
    case Cons(h,t)=>f(h,foldRight(t,b)(f))
  }

  @tailrec
  def foldLeft[A,B](l:List[A],b:B)(f:(A,B)=>B): B = l match  {
    case Nil => b
    case Cons(h,t)=>foldLeft(t,f(h,b))(f)
  }

  def sumV2(l:List[Int]):Int=foldRight(l,0)((a,b)=>a+b)

  def productV2(l:List[Double]):Double=foldRight(l,1.0)((a,b)=>a*b)

  def length[A](as:List[A]):Int=foldLeft(as,0)((_,i)=>i+1)

  def reverse[A](as:List[A]):List[A]=foldLeft(as,Nil:List[A])((a,b)=>Cons(a,b))

  def append[A](l:List[A],as:List[A]):List[A]=foldRight(l,as)(Cons(_,_))

  def concat[A](l:List[List[A]]):List[A]=foldRight(l,Nil:List[A])(append)
}

